home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / obj2asm.zip / OUINSERT.C < prev    next >
Text File  |  1991-10-02  |  7KB  |  172 lines
  1. #include <stdio.h>
  2. #include "o.h"
  3.  
  4. void swap( NODE_T *, int, NODE_T *, int );
  5.  
  6. void swap( node_A, direct_A, node_B, direct_B )
  7.     NODE_T  *node_A;
  8.     int     direct_A;
  9.     NODE_T  *node_B;
  10.     int     direct_B;
  11. {
  12.     /* Swap the pointers (unless they are already threads) */
  13.     if ( node_A->thread[direct_A] ) {
  14.         node_B->ptr[direct_B] = node_A;
  15.         node_B->thread[direct_B] = TRUE;
  16.         node_A->thread[direct_A] = FALSE;
  17.     } else {
  18.         node_B->ptr[direct_B] = node_A->ptr[direct_A];
  19.         node_A->ptr[direct_A] = node_B;
  20.     }
  21. }
  22.  
  23. /*
  24.   void   *data;                       pointer to data struct to save
  25.   NODE_T *root_node;                  pointer to root node
  26.   int    (*cmp_routine)(void*,void*); routine used to compare values at 2 nodes
  27. */
  28.  
  29. NODE_T *insert( void *data, NODE_T *root_node, int (*cmp_routine)(void*,void*))
  30. {
  31.     NODE_T      *insert_node;
  32.     NODE_T      *curr_node;         /* Current node we are visiting      */
  33.     NODE_T      *son_node;
  34.     NODE_T      *grand_son;
  35.     NODE_T      *path[32];          /* 32 levels (2^32 records!) */
  36.     int         direct[32];
  37.     int         level;
  38.     int         curr_direct;
  39.     int         con_direct;
  40.  
  41.     /* Prepare initial value for tree traversal */
  42.     level    = 0;
  43.     son_node = root_node;
  44.  
  45.     /*
  46.     **  Traverse tree looking for the place to insert this new node.  If
  47.     **  we find a node which gives a comparison result of 0 (equal), then
  48.     **  we cannot insert this new node.  To indicate this duplicate value,
  49.     **  a pointer to the node which contains the duplicate value is returned.
  50.     */
  51.     do  {
  52.         curr_node = son_node;               /* Advance to new son_node */
  53.  
  54.         /*  Compare this new node with the node at this position in the
  55.             tree and determine which direction to proceed from here.
  56.         */
  57.         curr_direct = (* cmp_routine)( curr_node->data, data );
  58.  
  59.         /*  is this node is a duplicate node?
  60.         */
  61.         if ( curr_direct == EQUAL ) {
  62.             if ( root_node->balance == LEFT ) { /* Duplicates allowed? */
  63.                 curr_direct = LEFT;             /* see new_tree()!!!!  */
  64.             } else {
  65.                 return ( curr_node );
  66.             }
  67.         }
  68.  
  69.         path[level] = curr_node;
  70.         direct[level] = curr_direct;
  71.         level++;
  72.  
  73.         son_node = curr_node->ptr[curr_direct];
  74.  
  75.     } while ( !curr_node->thread[curr_direct]);
  76.  
  77.     /*  Now, we have found the place to insert this node,
  78.         make the last visited node point to this new node.
  79.     */
  80.     con_direct = 1-curr_direct;
  81.  
  82.     /* Set up default values for this node which we are going to insert */
  83.     insert_node = (NODE_T *)o_malloc( sizeof(NODE_T) );
  84.  
  85.     insert_node->data                = data;
  86.     insert_node->balance             = BALANCED;
  87.     insert_node->thread[curr_direct] = TRUE;
  88.     insert_node->thread[con_direct ] = TRUE;
  89.     insert_node->ptr   [curr_direct] = curr_node->ptr[curr_direct];
  90.     insert_node->ptr   [con_direct ] = curr_node;
  91.  
  92.     curr_node->thread  [curr_direct] = FALSE;
  93.     curr_node->ptr     [curr_direct] = insert_node;
  94.  
  95.  
  96.     /*  Now loop through 'un-stacking' the path which we took on our
  97.         way to get this guy inserted.  Keep in mind that this process
  98.         is done in stack-order, so the last node visited will be the
  99.         first node processed, etc.  Also keep in mind that the loop
  100.         may be terminated before back-tracking completely to the root
  101.         node (ie. the entire path is not processed).
  102.     */
  103.     do {
  104.         son_node = curr_node;
  105.  
  106.         level--;
  107.  
  108.         /*  If we have gotten back out to the root of the tree,
  109.             then the height of the tree has increase.
  110.         */
  111.         if ( level == 0 ) {         /* Increment depth (see new_tree()!!!) */
  112.             root_node->ptr[LEFT] = (NODE_T *) (((int)root_node->ptr[LEFT])+1);
  113.             break;
  114.         }
  115.  
  116.         /*  Get path information at this stack level
  117.         */
  118.         curr_node = path[level];
  119.         curr_direct = direct[level];
  120.  
  121.         /*  If the node at this position along the path was BALANCED,
  122.             then make it lean in the direction we took from it on our
  123.             way down.
  124.         */
  125.         if ( curr_node->balance == BALANCED ) {
  126.             curr_node->balance = curr_direct;
  127.         } else {
  128.             /*  Otherwise, two cases may arise.
  129.                 1.  The node was unbalanced in the opposite
  130.                     direction to the direction we took.
  131.                     (In this case that node will become balanced)
  132.             */
  133.             if ( curr_node->balance != curr_direct ) {
  134.                 curr_node->balance = BALANCED;
  135.                 break;
  136.             } else {
  137.                 /* or 2.  The node was already unbalanced in the same
  138.                           direction we took. If this happens we may need to
  139.                           do single or double rotation.  Single rotation
  140.                           happens if the node (which is in the opposite
  141.                           direction to the direction we took) is leaning
  142.                           the direction we took (from the current node).
  143.                           Otherwise to double rotation.
  144.                 */
  145.                 con_direct = 1 - curr_direct;
  146.                 if ( son_node->balance == curr_direct ) {
  147.                     swap( son_node, con_direct, curr_node, curr_direct );
  148.                     curr_node->balance = BALANCED;
  149.                 } else {
  150.                     grand_son = son_node->ptr[con_direct];
  151.                     swap( grand_son, curr_direct,  son_node,  con_direct );
  152.                     swap( grand_son,  con_direct, curr_node, curr_direct );
  153.                     son_node->balance = (grand_son->balance == con_direct) ?
  154.                                             curr_direct : BALANCED;
  155.                     curr_node->balance = (grand_son->balance == curr_direct) ?
  156.                                             con_direct : BALANCED;
  157.                     son_node = grand_son;
  158.                 }
  159.                 son_node->balance = BALANCED;
  160.  
  161.                 /* now make parent point to new rotated node */
  162.                 path[level-1]->ptr[direct[level-1]] = son_node;
  163.                 break;
  164.             }
  165.         }
  166.     } while ( TRUE );
  167.  
  168.     /*  Return a pointer to the node inserted */
  169.     return ( insert_node );
  170. }
  171.  
  172.